/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 * 二叉树的任意路径求最大和
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月17日
 */
public class BinaryTreeMaximumPathSum {

    public int maxPathSum(TreeNode root) {
        List<Integer> maxSum = new ArrayList<>();
        maxSum.add(Integer.MIN_VALUE);
        //ArrayList可以用来传参，作为子树的最大路径和
        getMaxSum(root, maxSum);
        return maxSum.get(0);
    }

    /**
     * 
     * @param root
     * @param maxSum
     * @author towan
     * 2015年6月17日
     */
    private int getMaxSum(TreeNode root, List<Integer> maxSum) {
        if(root==null){
            return 0;
        }
        int leftSum = 0;
        int rightSum = 0;
        
        //左右子树各返回两个结果，以子树为结尾的最大路径和以及子树下所有路径的最大值
        leftSum = getMaxSum(root.left, maxSum);
        rightSum = getMaxSum(root.right, maxSum);
        
        int curSum = Math.max(root.val, root.val+Math.max(rightSum, leftSum));
        maxSum.set(0, Math.max(maxSum.get(0), Math.max(curSum, root.val+leftSum+rightSum)));
        return curSum;
    }
    
}
